/**
 *  @file HashTableT.h
 */
#ifndef _HASHTABLET_H_
#define _HASHTABLET_H_

#include "../common/CppMemPool.h"
#include "ArrayT.h"
#include "ListT.h"

namespace cppflib
{

namespace collections
{

/**
 *   Hashtable
 *
 *   @note KEYT and VALT should be class derived from BaseObject
 */
template <class KEYT, class VALT>
class HashtableT : public BaseObject
{
   PRIVATE const u32_t DEFAULTSIZE = 17;
 
   //! structure to hold key and value pairs
   typedef struct 
   {
      BaseObject * pKey;
      BaseObject * pVal;
   } slot_t;

private:
   ArrayCppObjT<ListT<ptr_t> > *pHashSlots;  ///< array of lists
   

   void InitHashSlots(u32_t nrSlots)
   {
      pHashSlots = new ArrayCppObjT<ListT<ptr_t> >(nrSlots);
      cppmempool::Retain(pHashSlots);

      // init each slot with an empty list
      for (u32_t i = 0; i < pHashSlots->GetSize(); ++i) {
         ListT<ptr_t> *pList = new ListT<ptr_t>();         
         pHashSlots->Set(static_cast<int>(i), pList);
      }
   }  

   int GetSlotIndex(const KEYT &key) const
   {
      return static_cast<int>(key.GetHash() % pHashSlots->GetSize());
   }  

   void RemoveSlotByIndex(ListT<ptr_t> *pList, int nIndex)
   {
      slot_t *pSlot = reinterpret_cast<slot_t*>(pList->RemoveAt(nIndex));
      cppmempool::Release(pSlot->pKey);
      cppmempool::Release(pSlot->pVal);
      ::MRP_Release(pSlot);
   }

   /**
    *  Add a pair of key and val (KEYT must implement BaseObject::GetHash)
    *
    *  @param [in] pKey -- key can't be NULL
    *  @param [in] pVal -- value can be NULL
    */
   void Add(KEYT *pKey, VALT *pVal)
   {
      if (!pKey)
         return;

      cppmempool::Retain(pKey);
      cppmempool::Retain(pVal);

      slot_t *pNewSlot = static_cast<slot_t*>(::MRP_Calloc(1, sizeof(slot_t)));
      pNewSlot->pKey = pKey;
      pNewSlot->pVal = pVal;

      int nSlot = GetSlotIndex(*pKey);
      ListT<ptr_t> *pList = pHashSlots->Get(nSlot);
      pList->AddTail(reinterpret_cast<ptr_t>(pNewSlot));
   }
   
public:
   HashtableT(void)
   {
      InitHashSlots(DEFAULTSIZE);
   }

   /**
    *  Init hash with a specified capacity (number of slots in the hash table. It's best to
    *  be a prime number)
    */
   explicit HashtableT(u32_t capacity)
   {
      InitHashSlots(capacity);
   }

   virtual ~HashtableT()
   {
      Clear();

      // remove list and the hash array itself
      for (int i = 0; i < static_cast<int>(pHashSlots->GetSize()); ++i) {
         pHashSlots->Remove(i);
      }

      cppmempool::Release(pHashSlots);
   }

   

   /**
    *  Remove all elements
    *
    *  The internal array and lists are not removed
    */
   void Clear()
   {
      for (int i = 0; i < static_cast<int>(pHashSlots->GetSize()); ++i) {
         ListT<ptr_t> *pList = pHashSlots->Get(i);

         while (pList->GetCount() > 0) {
            RemoveSlotByIndex(pList, 0);
         }
      }
   }

   /**
    *  Remove element with the same key (KEYT must implement BaseObject::Equals)
    *
    *  @return true -- element is removed
    */
   bool Remove(const KEYT &key)
   {
      int nSlot = GetSlotIndex(key);
      ListT<ptr_t> *pList = pHashSlots->Get(nSlot);

      for (int i = 0; i < static_cast<int>(pList->GetCount()); ++i) {
         slot_t *pSlot = reinterpret_cast<slot_t*>(pList->Get(i));
         if (pSlot->pKey->Equals(key)) {
            RemoveSlotByIndex(pList, i);
            return true;
         }
      }

      return false;
   }

   /**
    *  Get value by key
    */
   VALT *Get(const KEYT &key) const
   {
      int nSlot = GetSlotIndex(key);
      ListT<ptr_t> *pList = pHashSlots->Get(nSlot);

      for (int i = 0; i < static_cast<int>(pList->GetCount()); ++i) {
         slot_t *pSlot = reinterpret_cast<slot_t*>(pList->Get(i));
         if (pSlot->pKey->Equals(key)) {
            return static_cast<VALT*>(pSlot->pVal);
         }
      }

      return NULL;
   }

   /**
    *  Set value of a key. If key already exists, original value will be overwritten, otherwise, 
    *  a new element is created.
    *
    *  @param [in] pKey -- key can't be NULL
    *  @param [in] pVal -- value can be NULL
    */
   void Set(KEYT *pKey, VALT *pVal)
   {
      if (!pKey)
         return;

      int nSlot = GetSlotIndex(*pKey);
      ListT<ptr_t> *pList = pHashSlots->Get(nSlot);
      bool isFound = false;

      // find if there is an element with the same key
      for (int i = 0; i < static_cast<int>(pList->GetCount()); ++i) {
         slot_t *pSlot = reinterpret_cast<slot_t*>(pList->Get(i));
         if (pSlot->pKey->Equals(*pKey)) {
            // replace value with a new one
            cppmempool::Retain(pVal);
            cppmempool::Release(pSlot->pVal);
            pSlot->pVal = pVal;
            isFound = true;
            break;
         }
      }

      if (!isFound)
         this->Add(pKey, pVal);
   }

   /**
    *  Get total number of elements in this hash table
    */
   u32_t GetCount() const
   {
      u32_t count = 0;

      for (int i = 0; i < static_cast<int>(pHashSlots->GetSize()); ++i) {
         count += pHashSlots->Get(i)->GetCount();
      }

      return count;
   }

   /**
    *  Test whether a key exists
    *
    *  @param [in] key -- the key to search
    */
   bool ContainsKey(const KEYT &key) const
   {
      int nSlot = GetSlotIndex(key);
      ListT<ptr_t> *pList = pHashSlots->Get(nSlot);

      for (int i = 0; i < static_cast<int>(pList->GetCount()); ++i) {
         slot_t *pSlot = reinterpret_cast<slot_t*>(pList->Get(i));
         if (pSlot->pKey->Equals(key)) {
            return true;
         }
      }

      return false;
   }

   /**
    *  Test whether a value exists
    *
    *  @param [in] val -- the value to search
    */
   bool ContainsValue(const VALT &val) const
   {
      for (int i = 0; i < static_cast<int>(pHashSlots->GetSize()); ++i) {
         ListT<ptr_t> *pList = pHashSlots->Get(i);

         for (int j = 0; j < static_cast<int>(pList->GetCount()); ++j) {
            slot_t *pSlot = reinterpret_cast<slot_t*>(pList->Get(j));
            // pVal is allowed to be NULL
            if (pSlot->pVal && pSlot->pVal->Equals(val)) {
               return true;
            }
         }
      }

      return false;
   }

   /**
    *  To enumerate all elements in this hash table. Call this function repeatedly
    *  until all elements are returned
    *
    *  @param [in,out] pos -- pass 0 on first call. On return, it is updated to point to next
    *                         element so pass it again without modification on subsequent calls 
    *                         until all elements have been enumerated (return false).
    *  @param [out] pKey -- contains pointer to the key of an element. Pass NULL if not interested
    *  @param [out] pVal -- contains pointer to the value of an element. Pass NULL if not interested
    *
    *  @return true -- if an element is returned
    *  @return false -- no element is returned, which means the end of the hashtable is reached.
    */
   bool EnumerateElement(u64_t &pos, const KEYT **pKey, VALT **pVal) const
   {
      if (pKey) *pKey = NULL;
      if (pVal) *pVal = NULL;

      u32_t hashSlot = 0, listIndex = 0;
      if (pos == 0L) {
         hashSlot = 0;
         listIndex = 0;
      }
      else {
         // high 32 bit is hashSlot, low 32 bit is listIndex
         hashSlot = static_cast<u32_t>((pos >> 32) & U64N(0xffffffff));
         listIndex = static_cast<u32_t>(pos & U64N(0xffffffff));
      }

      do {
         if (hashSlot >= pHashSlots->GetSize())
            break;

         ListT<ptr_t> *pList = pHashSlots->Get(hashSlot);
         if (pList->GetCount() == 0 || pList->GetCount() <= listIndex) {
            listIndex = 0; // must restart from beginning of a list
            
            // find a list with at least one element
            ++hashSlot;
            while (hashSlot < pHashSlots->GetSize()) {
               pList = pHashSlots->Get(hashSlot);
               if (pList->GetCount() > 0)
                  break;

               ++hashSlot;
            }

            if (hashSlot >= pHashSlots->GetSize()) // alreay reach end of hashtable
               pList = NULL;
         }
         
         if (!pList)
            break;

         // update on return
         slot_t *pSlot = reinterpret_cast<slot_t*>(pList->Get(listIndex));
         if (pKey) *pKey = static_cast<KEYT*>(pSlot->pKey);
         if (pVal) *pVal = static_cast<VALT*>(pSlot->pVal);

         ++listIndex; // advance to next element
         pos = (static_cast<u64_t>(hashSlot) << 32) | (static_cast<u64_t>(listIndex) & U64N(0xffffffff));
         
         return true;

      } while(false);


      return false;
   }

   /**
    *  Make a copy of itself -- key and value are just shallow copies
    */
   HashtableT<KEYT, VALT> * Copy() const
   {
      u64_t pos = 0;
      const KEYT *pKey;
      VALT *pVal;
      HashtableT<KEYT, VALT> * pCopyHash = new HashtableT<KEYT, VALT>(pHashSlots->GetSize());
      while (EnumerateElement(pos, &pKey, &pVal)) {
         pCopyHash->Set(const_cast<KEYT*>(pKey), pVal);
      }

      return pCopyHash;
   }

};

} // end of namespace collections


} // end of namespace cppflib


#endif
